Covering cubes by hyperplanes

Abstract: Note that the vertices of the $n$-dimensional cube $\{0, 1\}^n$ can be covered by two affine hyperplanes $x_1=1$ and $x_1=0$. However if we leave one vertex uncovered, then suddenly at least $n$ affine hyperplanes are needed. This was a classical result of Alon and F\"uredi, followed from the Combinatorial Nullstellensatz.

In this talk, we consider the following natural generalization of the Alon-F\"uredi theorem: what is the minimum number of affine hyperplanes such that the vertices in $\{0, 1\}^n \setminus \{\vec{0}\}$ are covered at least $k$ times, and $\vec{0}$ is uncovered? We answer the problem for $k \le 3$ and show that a minimum of $n+3$ affine hyperplanes is needed for $k=3$, using a punctured version of the Combinatorial Nullstellensatz. We also develop an analogue of the Lubell-Yamamoto-Meshalkin inequality for subset sums, and solve the problem asymptotically for fixed $n$ and $k \rightarrow \infty$, and pose a conjecture for fixed $k$ and large $n$.

Joint work with Alexander Clifton (Emory University).

combinatorics

Audience: researchers in the topic

Comments: password 121323

---

SCMS Combinatorics Seminar

Series comments: Check scmscomb.github.io/ for more information

---